package algrithm;

import java.util.Arrays;

/**
 * 快速排序的实现
 *
 * @author: cuiH
 * Date: 13-12-8
 */
public class QuickSort {

    public static void main(String[] args) {
        int[] list={34,3,53,2,23,7,14,10};
        new QuickSort().quickSort(list);
    }

    public void quickSort(int[] needSort){
        if(needSort.length<=0) return;
        sortByPosition(needSort, 0, needSort.length - 1);
        System.out.println(Arrays.toString(needSort));
    }

    private void sortByPosition(int[] needSort, int startPosition, int endPosition) {
        if(startPosition<endPosition){
            int middle = getMiddle(needSort,startPosition,endPosition);
            sortByPosition(needSort,startPosition,middle-1);
            sortByPosition(needSort,middle+1,endPosition);
        }
    }

    private int getMiddle(int[] needSort, int startPosition, int endPosition) {
        int temp = needSort[startPosition];
        while (startPosition<endPosition){
            while(startPosition < endPosition && needSort[endPosition] > temp){
                endPosition--;
            }
            needSort[startPosition] = needSort[endPosition];
            while (startPosition < endPosition && needSort[startPosition] < temp){
                endPosition++;
            }
            needSort[endPosition] = needSort[startPosition];
        }
        needSort[startPosition] = temp;              //中轴记录到尾
        return startPosition;                   //返回中轴的位置
    }
}